package com.origin.niuke.dynamic;

/**
 * NC164 最长上升子序列(二)
 * 算法：动态规划 + 二分查找 + 贪心
 * 定义一个 tail 数组, 遍历时
 * 1、如果当前元素比 tail 数组中的最后一个数还大, 直接将当前元素加到 tail 数组的后面
 * 2、如果当前元素比 tail 数组中的最后一个数还小, 将比第一个比当前元素还大的数用当前元素替换
 * 这样，tail 中的元素都是比较小的数，加入进来的数也会越多
 *
 * @author yezh
 * @date 2022/12/21 20:56
 */
public class NC164 {

    public int LIS (int[] a) {
        // write code here
        int ans = 0, n = a.length, len = 0;
        int[] tail = new int[n];
        for (int i = 0; i < n; i++) {
            if (i == 0 || a[i] > tail[len - 1]) {
                tail[len++] = a[i];
                ans = Math.max(ans, len);
            } else {
                int idx = binarySearch(tail, len, a[i]);
                tail[idx] = a[i];
                ans = Math.max(ans, idx);
            }
        }
        return ans;
    }

    int binarySearch(int[] tail, int len, int target) {
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (tail[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

}
